package bestTimetoBuyandSellStockwithCooldown;

public class Solution {
    public int maxProfit(int[] prices) {
        int[][] f=new int[prices.length][2];
        if (prices.length==0) return 0;
        int ans=0;
        f[0][0]=-prices[0];
        f[0][1]=0;
        for (int i=1;i<prices.length;i++){
        	if (i>=2) f[i][0]=Integer.max(f[i-1][0]+prices[i-1]-prices[i],f[i-2][1]-prices[i]);
        	else f[i][0]=-prices[i];
        	if (i>=2) f[i][1]=Integer.max(f[i-1][1]-prices[i-1]+prices[i], f[i-1][0]+prices[i]);
        	else f[i][1]=f[i-1][0]+prices[i];
        	ans=Integer.max(ans, f[i][1]);
        }
        return ans;
    }
}

/*309. Best Time to Buy and Sell Stock with Cooldown
 * 题目大意：给一样货物n天的价格，同一天只能买或卖，不能同时持有多件货物，不能再卖出后的第二天进行买入
 * DP核心：状态转移
 * 第i天若进行买入，则买入操作的可能最优解有
 * 1.第i-1天买入但“后悔”，改为第i天买入
 * 2.第i-2天卖出，一天cooldown后进行买入
 * 第i天若进行卖出，则卖出操作的可能最优解有
 * 1.第i-1天卖出但“后悔”，改为第i天卖出
 * 2.第i-1天买入，第i天卖出
 * 
 * 
 */
